package com.lili.dt;

/**
 * @Auther: 李 力
 * @Date: 2024/8/7
 * @Description: 斐波拉契数列
 * @version: 1.0
 */
public class Fibonacci {

    /*
     *  老办法:递归
     *
     *
     * */
    public static int getFibonacci(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        return getFibonacci(n - 1) + getFibonacci(n - 2);
    }

    /*
     *  从已知子问题的解，推导出当前问题的解
     *  推到过程可以表达为一个数学公式
     *  用一维数组或者二维数组来保存之前的计算结果
     * */
    public static int getFibonacci2(int n) {
        //缓存结果
        int[] dp = new int[n + 1];
        if (n == 0) {
            dp[0] = 0;
            return 0;
        }
        if (n == 1) {
            dp[1] = 1;
            return 1;
        }
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    //降维
    public static int getFibonacci3(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        //用局部变量保存值
        int a = 0;//前一项的和
        int b = 1;//前2项的和
        for (int i = 2; i <= n; i++) {
            int c = a + b;//当前项的值
            a = b; //往后移动
            b = c;//往后面移动
        }
        return b;//最后一次循环已经把c赋值给了b
    }
}
